package com.kehao.leetcode.jzoffer;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class JZSolution057 {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        Map<Long,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            long index = getIndex(nums[i],t);
            if(map.get(index)!=null&&i-map.get(index)<=k){
                return true;
            }
            Integer left = map.get(index -1);
            if(left!=null&&i-left<=k&&(long)nums[i]-nums[left]<=t){
                return true;
            }
            Integer right = map.get(index + 1);
            if(right!=null&&i-right<=k&&(long)nums[right]-nums[i]<=t){
                return true;
            }
            map.put(index,i);
        }
        return false;
    }

    private long getIndex(long num, long t) {
        if(num>=0) return num/(t+1);
        else return num/(t+1)-1;
    }

    @Test
    public void test01(){
        int[] nums = {2147483647,-1,2147483647};
        int k =1;
        int t= 2147483647;
        boolean result = containsNearbyAlmostDuplicate(nums, k, t);
        System.out.println(result);
    }
}
